package leetcode.code0855;

import java.util.TreeSet;

public class ExamRoom {

	int n;

	TreeSet<Integer> ts;

	public ExamRoom(int n) {
		this.n = n - 1;
		this.ts = new TreeSet<>();
	}

	public int seat() {
		int last = Integer.MAX_VALUE, max = 0;
		int start = 0;
		for (int seat : ts) {
			if (((seat - last) >> 1) > max) {
				start = last;
				max = ((seat - last) >> 1);
			}
			last = seat;
		}
		if ((this.n - last) > max) {
			max = this.n - last;
			start = last;
		}
		int ans = start + max;
		if (ts.isEmpty() || ts.first() >= max) {
			ans = 0;
		}
		ts.add(ans);// 
		return ans;
	}

	public void leave(int p) {
		ts.remove(p);
	}

	public static void main(String[] args) {

		ExamRoom er = new ExamRoom(10);
		er.seat();
		er.seat();
		er.seat();
		er.seat();
		er.leave(0);
		er.leave(4);
		er.seat();
		er.seat();
		er.seat();
		er.seat();
		er.seat();
		er.seat();
		er.seat();
		er.seat();
		er.seat();
	}

}
